/**
 * 
 */
package dp;

import java.util.Arrays;

/**
 * Given a string S and a string T, find the minimum window in S which will
 * contain all the characters in T in complexity O(n).
 * 
 * For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "window:ADOBEC".
 * 
 * Note: If there is no such window in S that covers all characters in T, return
 * the emtpy string "".
 * 
 * If there are multiple such windows, you are guaranteed that there will always
 * be only one unique minimum window in S.
 * 
 * @author xyyi
 * @since 2013/01/13
 * @version 2013/01/13
 * @see
 */
public class MinimumWindowSubstringOrdered {

	/**
	 * 
	 */
	public MinimumWindowSubstringOrdered() {
		// TODO Auto-generated constructor stub
	}

	/**
	 *     A   B   C   #  T[j]
	 * A   6   6   5   0
	 * D   n   5   4   0
	 * O   n   4   4   0
	 * B   n   3   3   0
	 * E   n   9   2   0
	 * C   n   8   1   0
	 * O   n   7   7   0
	 * D   n   6   6   0
	 * E   n   5   5   0
	 * B   n   4   4   0
	 * A   n   n   3   0
	 * N   n   n   2   0
	 * C   n   n   1   0
	 * #   n   n   n   0
	 * S[i]
	 * 
	 * dp[i][j] = dp[i+1][j+1] + 1 if S[i] = T[j]
	 * dp[i][j] = dp[i+1][j] + 1 if S[i] != T[j]
	 * 
	 * 
	 */

	private final static int EMPTY = -1;
	private final static int NO_MATCH = -2;

	public void minWindowsRecursion(char[] S, char[] T) {
		int[][] dp = new int[S.length + 1][T.length + 1];
		for (int i = 0; i <= S.length; i++) {
			Arrays.fill(dp[i], EMPTY); // -1 means empty, -2 means not match
			dp[i][T.length] = 0;
		}

		minWindowsRecursionHelp(S, T, 0, 0, dp);

		int minIndex = -1;
		for (int i = 0; i < S.length; i++) {
			if (dp[i][0] > 0 && (minIndex == -1 || dp[i][0] < dp[minIndex][0])) {
				minIndex = i;
			}
		}

		if (minIndex >= 0) {
			System.out.println("start:" + minIndex);
			System.out.println("len:" + dp[minIndex][0]);
			System.out.println("window:"
					+ String.valueOf(S).substring(minIndex,
							minIndex + dp[minIndex][0]));
		}
	}

	private int minWindowsRecursionHelp(char[] S, char[] T, int i, int j,
			int[][] dp) {

		if (i == S.length || j == T.length) {
			return dp[i][j];
		}
		if (i == S.length) {
			return NO_MATCH;
		}

		if (S[i] == T[j]) {
			if (dp[i + 1][j + 1] == EMPTY) {
				dp[i + 1][j + 1] = minWindowsRecursionHelp(S, T, i + 1, j + 1,
						dp);
			}
			if (dp[i + 1][j + 1] != NO_MATCH) {
				dp[i][j] = dp[i + 1][j + 1] + 1;
			}
		} else {
			if (dp[i + 1][j] == EMPTY) {
				dp[i + 1][j] = minWindowsRecursionHelp(S, T, i + 1, j, dp);
			}
			if (dp[i + 1][j] != NO_MATCH) {
				dp[i][j] = dp[i + 1][j] + 1;
			}
		}
		if (dp[i][j] == EMPTY) {
			dp[i][j] = NO_MATCH;
		}

		return dp[i][j];
	}

	void minWindowsDP(char[] S, char[] T) {
		int m = S.length;
		int n = T.length;
		int[][] dp = new int[m + 1][n + 1];
		int minIndex = -1;

		for (int i = 0; i <= S.length; i++) {
			Arrays.fill(dp[i], EMPTY);
			dp[i][n] = 0;
		}

		for (int i = m - 1; i >= 0; i--) {
			for (int j = n - 1; j >= Math.max(0, n - (m - i)); j--) {
				if (S[i] == T[j]) {
					if (dp[i + 1][j + 1] != EMPTY) {
						dp[i][j] = dp[i + 1][j + 1] + 1;
					}
				} else if (dp[i + 1][j] != EMPTY) {
					dp[i][j] = dp[i + 1][j] + 1;
				}
			}
			// if (dp[i][0] >= 0 && (minIndex == -1 || dp[i][0] <
			// dp[minIndex][0]))
			// minIndex = i;

			if (dp[i][0] >= 0 && (minIndex == -1 || dp[i][0] < dp[minIndex][0])) {
				minIndex = i;
			}
		}

		if (minIndex >= 0) {
			System.out.println("start:" + minIndex);
			System.out.println("len:" + dp[minIndex][0]);
			System.out.println("window:"
					+ String.valueOf(S).substring(minIndex,
							minIndex + dp[minIndex][0]));
		}
	}

	void minWindows(char[] S, char[] T) {
		int m = S.length;
		int n = T.length;
		int[][] dp = new int[m + 1][n + 1];
		int minindex = -1;

		for (int i = 0; i <= m; i++) {
			Arrays.fill(dp[i], -1);
			dp[i][n] = 0;
		}

		for (int i = m - 1; i >= 0; i--) {
			for (int j = n - 1; j >= Math.max(0, n - (m - i)); j--)
				if (S[i] == T[j] && dp[i + 1][j + 1] >= 0)
					dp[i][j] = dp[i + 1][j + 1] + 1;
				else if (dp[i + 1][j] >= 0)
					dp[i][j] = dp[i + 1][j] + 1;
			if (dp[i][0] >= 0 && (minindex == -1 || dp[i][0] < dp[minindex][0]))
				minindex = i;
		}

		if (minindex >= 0) {
			System.out.println("start:" + minindex);
			System.out.println("len:" + dp[minindex][0]);
			System.out.println("window:"
					+ String.valueOf(S).substring(minindex,
							minindex + dp[minindex][0]));
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MinimumWindowSubstringOrdered mwso = new MinimumWindowSubstringOrdered();
		String s = "ADOBECODEBANC";
		String t = "ABC";

		mwso.minWindowsDP(s.toCharArray(), t.toCharArray());

	}

}
